//
// Created by Administrator on 2022/7/9.
//
//建立中序线索树
#include "Tree.cpp"
TreeNode * pre=NULL;
void inthread(Tree root){
    if(root!=NULL){
        //线索化左子树
        inthread(root->leftChild);
        //置前驱线索
        if(root->leftChild==NULL){
            root->leftTag=1;
            root->leftChild=pre;
        }
        //置后继线索
        if(pre!=NULL&&pre->rightChild==NULL){
            pre->rightTag=1;
            pre->rightChild=root;
        }
        //当前访问结点为下一访问结点的前驱
        pre=root;
        //线索化右子树
        inthread(root->rightChild);
    }
}
//中序线索二叉树找前驱
TreeNode * inpre(Tree root){
    //如果该节点有前驱线索 就直接返回其左孩子
    //否则找他的左子树中最右下端节点
    TreeNode *pre;
    if(root->leftTag==1){
        pre=root->leftChild;
    }else{
        TreeNode *q=root->leftChild;
        while(q->rightTag==0){
            q=q->rightChild;
        }
        pre=q;
    }
    return pre;
}
//中序线索二叉树找后继
TreeNode * innext(Tree root){
    //如果节点有后继线索，就直接返回右孩子
    //否则找他的右子树中最左下结点
    TreeNode * next;
    if(root->rightTag==1){
        next=root->rightChild;
    }else{
        TreeNode *q=root->rightChild;
        while(q->leftTag==0){
            q=q->leftChild;
        }
        next=q;
    }
    return next;
}
//先序线索二叉树找后继
TreeNode * prenext(Tree root){
    //如果节点有右线索 返回右孩子
    //如果结点没有右线索 如果有左孩子 返回左孩子
    //               如果没有左孩子 返回右孩子
    if(root->leftTag==0){
        return root->leftChild;
    }
}